#include <cstring>
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;

const int N = 1010;
int n, V, v[N], w[N];      // 全局不初始化默认就是0
// int dp[N][N];           // 可以开辟在栈上的空间更大
int dp[N];                 // 滚动数组优化 

int main() {

    while (cin >> n >> V) 
    {
        // 为了方便后续初始化，这里下标从1开始计数
        // 读取用户输入
        for (int i = 1; i <= n; i++) 
            cin >> v[i] >> w[i];
        /*下面是利用滚动数组进行优化的写法，时间复杂度是O(nV)的，空间复杂度是O(V)*/
        // 第一问
        for (int i = 1; i <= n; i++) 
            for (int j = V; j >= v[i]; j--) 
                dp[j] = max(dp[j], w[i] + dp[j - v[i]]);
        cout << dp[V] << endl;

        // 第二问
        memset(dp, 0, sizeof dp);

        // dp[0][j]表示没有物品，且要正好装满j容量的情况，这种情况不可能存在，我们规定为-1
        for (int j = 1; j <= V; j++) dp[j] = -1;

        for (int i = 1; i <= n; i++) 
            for (int j = V; j >= v[i]; j--) 
                if (dp[j - v[i]] != -1)
                    dp[j] = max(dp[j], w[i] + dp[j - v[i]]);   
        cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

        /*下面是常规写法，时空复杂度都是O(nV)的*/
        /*
        // 第一问
        for (int i = 1; i <= n; i++) 
        {
            for (int j = 1; j <= V; j++) 
            {
                dp[i][j] = dp[i - 1][j];    // 不选i这个物品
                if (j - v[i] >= 0)
                    dp[i][j] = max(dp[i][j], w[i] + dp[i - 1][j - v[i]]);   // 选i物品
            }
        }
        cout << dp[n][V] << endl;

        // 第二问
        memset(dp, 0, sizeof dp);

        // dp[0][j]表示没有物品，且要正好装满j容量的情况，这种情况不可能存在，我们规定为-1
        for (int j = 1; j <= V; j++) dp[0][j] = -1;

        for (int i = 1; i <= n; i++) 
        {
            for (int j = 1; j <= V; j++) 
            {
                dp[i][j] = dp[i - 1][j];    // 不选i这个物品
                if (j - v[i] >= 0 && dp[i - 1][j - v[i]] != -1)
                    dp[i][j] = max(dp[i][j], w[i] + dp[i - 1][j - v[i]]);   // 选i物品
            }
        }
        cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

    */
    }
    return 0;
}